#define _CRT_SECURE_NO_WARNINGS 1
typedef pair<int, int> PII;
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        stack<PII> st;
        st.push({ nums[0], 0 });
        int ans = 0;
        for (int i = 1; i < nums.size(); i++) {
            auto it = st.top();

            while (!st.empty() && st.top().first > nums[i]) {
                auto t = st.top();
                st.pop();
                int d = i - t.second;
                int r = i - 1;
                int l = 0;
                // ans=max(ans,i-t.second);
                if (!st.empty()) {
                    d += t.second - st.top().second - 1;
                    l = st.top().second + 1;
                }
                else {
                    d += t.second;
                    l = 0;
                }

                if (l <= k && r >= k) ans = max(ans, d * t.first);
            }
            st.push({ nums[i], i });
        }
        while (!st.empty()) {
            auto t = st.top();
            st.pop();
            int d = nums.size() - t.second;
            int r = nums.size() - 1;
            int l = 0;
            // ans=max(ans,i-t.second);
            if (!st.empty()) {
                d += t.second - st.top().second - 1;
                l = st.top().second + 1;
            }
            else {
                d += t.second;
            }
            if (l <= k && r >= k) ans = max(ans, d * t.first);
        }
        return ans;
    }
};
//
typedef pair<int, int> PII;
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        stack<PII> st;
        st.push({ nums[0], 0 });
        int ans = 0;
        int n = nums.size();
        vector<int> left(n);
        vector<int> right(n);
        for (int i = 1; i < nums.size(); i++) {
            auto it = st.top();
            while (!st.empty() && st.top().first > nums[i]) {
                auto t = st.top();
                st.pop();
                // int d = i - t.second;
                int r = i - 1;
                int l = 0;
                // ans=max(ans,i-t.second);
                if (!st.empty()) {
                    l = st.top().second + 1;
                }
                left[t.second] = l;
                right[t.second] = r;
                //if(l<=k&&r>=k) ans = max(ans, d * t.first);
            }
            st.push({ nums[i], i });
        }
        while (!st.empty()) {
            auto t = st.top();
            st.pop();
            // int d = nums.size() - t.second;
            int r = nums.size() - 1;
            int l = 0;
            // ans=max(ans,i-t.second);
            if (!st.empty()) {
                //d += t.second - st.top().second - 1;
                l = st.top().second + 1;
            }
            // if(l<=k&&r>=k) ans = max(ans, d * t.first);
            left[t.second] = l;
            right[t.second] = r;
        }


        for (int i = 0; i < n; i++) {
            if (left[i] <= k && right[i] >= k) {
                ans = max(ans, nums[i] * (right[i] - left[i] + 1));
            }
        }
        return ans;
    }
};